1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to memory management of computer systems using what has come to be known as “garbage collection.”
2. Description of the Related Art
In the field of computer systems, considerable effort has been expended on the task of allocating and managing memory. In general, memory may be allocated to data objects (which may also be referred to as data structures or records) either statically or dynamically. Some computer languages may require that memory be allocated for all the variables defined in a program statically, e.g., at compile time. Such static memory allocation may make it difficult to share available memory space among multiple applications, especially for applications that are long-lived. Abiding by space limitations may be easier when the platform provides support for dynamic memory allocation, e.g., when memory space to be allocated to a given object is determined only at run time.
Dynamic allocation has a number of advantages, among which is that the run-time system is able to adapt allocation to run-time conditions. For example, the programmer can specify that space should be allocated for a given object only in response to a particular run-time condition. The C-language library function malloc( ) is often used for this purpose. Conversely, the programmer can specify conditions under which memory previously allocated to a given object can be reclaimed for reuse. The C-language library function free( ) results in such memory reclamation. Because dynamic allocation provides for memory reuse, it facilitates generation of large or long-lived applications, which over the course of their lifetimes may employ objects whose total memory requirements would greatly exceed the available memory resources if they were bound to memory locations statically.
Particularly for long-lived applications, though, allocation and reclamation of dynamic memory must be performed carefully. If the application fails to reclaim unused memory—or, worse, loses track of the address of a dynamically allocated segment of memory—its memory requirements may grow over time to exceed the system's available memory. This kind of error is known as a “memory leak.” Another kind of error occurs when an application reclaims memory for reuse even though it still maintains a reference to that memory. If the reclaimed memory is reallocated for a different purpose, the application may inadvertently manipulate the same memory in multiple inconsistent ways. This kind of error is known as a “dangling reference.”
A way of reducing the likelihood of such leaks and related errors is to provide memory-space reclamation in a more automatic manner. Techniques used by systems that reclaim memory space automatically are commonly referred to as garbage collection. Garbage collectors operate by reclaiming space that they no longer consider “live” or “reachable.” (Unreachable space may be termed “garbage”, hence the name of the technique.) Statically allocated objects represented by a program's global variables are normally considered reachable throughout a program's life. Such objects are not ordinarily stored in the garbage collector's managed memory space, but they may contain references to dynamically allocated objects that are, and such objects are considered reachable. Clearly, an object referred to in the processor's call stack is reachable, as is an object referred to by register contents. And an object referred to by any reachable object is also reachable. As used herein, a call stack is a data structure corresponding to a process or thread (e.g., of an application), whereby the call stack comprises a sequence of frames that store state information, such as register contents and program counter values, associated with nested routines within the process or thread.
The use of garbage collectors is advantageous because, whereas a programmer working on a particular sequence of code can perform his task creditably in most respects with only local knowledge of the application at any given time, memory allocation and reclamation require a global knowledge of the program. Specifically, a programmer dealing with a given sequence of code does tend to know whether some portion of memory is still in use for that sequence of code, but it is considerably more difficult for him to know what the rest of the application is doing with that memory. By tracing references from some conservative notion of a root set, e.g., global variables, registers, and the call stack, automatic garbage collectors obtain global knowledge in a methodical way. By using a garbage collector, the programmer is relieved of the need to worry about the application's global state and can concentrate on local-state issues, which are more manageable. The result is applications that are more robust, having no dangling references and fewer memory leaks.
Garbage collection mechanisms can be implemented by various parts and levels of a computing system. One approach is simply to provide them as part of a batch compiler's output. In this approach to garbage collection, in addition to generating code for the functionality supported by an application, the batch compiler may generate code that automatically reclaims unreachable memory space without explicit direction from a the programmer, and include it within the application's object code. Even in this simple case, though, there is a sense in which the application does not itself provide the entire garbage collector. Specifically, the application will typically call upon the underlying operating system's memory-allocation functions. And the operating system may in turn take advantage of various hardware that lends itself particularly to use in garbage collection. So even a very simple system may disperse the garbage collection mechanism over a number of computer system layers.
Another approach to garbage collection may be taken in some systems that employ “virtual machines”. In such a system, a compiler or an interpreter may convert source code for an application from a high-level language to instructions called “byte code” for virtual machines that various processors can be configured to emulate. One example of a high-level language for which compilers and interpreters are available to produce such virtual-machine instructions is the Java™ programming language. (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Typically, byte-code routines are executed by a processor under control of a virtual-machine process, and the virtual machine process provides memory management functions including garbage collection. For example, a memory management component of the virtual machine process may be responsible for allocating memory dynamically as needed and reclaiming unreachable memory when possible. Various other approaches to garbage collection may be employed, including implementation of garbage collection functions in hardware.
While an implementation of automatic garbage collection can greatly reduce the occurrence of memory leaks and other software deficiencies, it can also have significant adverse performance effects if it is not implemented carefully. To distinguish the part of the program that does “useful” work from that which does the garbage collection, the term mutator is sometimes used for the “useful” part; from the collector's point of view, what the mutator does is mutate active data structures' connectivity. The instructions executed by the garbage collector are typically considered memory management overhead, and a variety of garbage collection techniques (such as various types of incremental garbage collection, generational garbage collection, etc.) have been devised to reduce the collection overhead relative to the “useful” work done by the mutator. In general, generational garbage collection refers to techniques where objects in the heap (i.e., the dynamically allocated memory) are segregated into different regions (or “generations”), for example based on how long ago the objects were allocated, and the different regions or generations are managed and collected separately. Generational garbage collection techniques may rely on the general assumption that the age of an object (i.e., how recently the object was originally allocated) affects the probability that the object will remain reachable; e.g., some generational garbage collectors may be configured to concentrate on preferentially collecting regions that contain relatively recently allocated (“young”) objects, as recently allocated objects are assumed to become unreachable more quickly than long-lived objects.
Mutator operations may be interleaved with garbage collection operations in a variety of ways—for example, a garbage collector may be periodically or aperiodically activated to perform what is called a garbage collection “cycle” or “interval”, during which a portion or all of the heap for a mutator may be examined for unreachable objects, and unreachable objects found may be reclaimed. After the interval completes, the garbage collector may be deactivated until the next interval is triggered, e.g., by a detection that insufficient heap memory remains free, or based on a schedule. The mutator may proceed with its operations concurrently with the garbage collection interval in some implementations, while in other implementations mutator operations may be suspended during at least a part of the garbage collection interval. Periods during which mutators are suspended may be termed “stop-world” pauses, and a garbage collection interval that requires mutators to remain suspended throughout the interval may also be termed a garbage collection “pause”. Some garbage collectors (which may be termed incremental collectors) may be configured to collect only a subset of the heap at one time, e.g., in order to reduce the impact of garbage collection on mutator performance. The subset of the heap that is collected during a given garbage collection interval may be termed the “collection set” for that interval. Incremental garbage collection may be combined with generational garbage collection in some algorithms; e.g., the subset of the heap collected during a particular collection interval may correspond to regions of a particular generation or a selected set of generations.
Many modern mutator applications may be characterized by large amounts of live (i.e., reachable) heap data and considerable thread-level parallelism, and may be run on high-end multiprocessor systems to achieve desired performance goals. In addition to throughput-oriented performance goals, certain classes of such applications may also have responsiveness constraints that may be described as “soft real time constraints”. For example, telecommunications call-processing applications may require that delays in setting up calls be limited to no more than a specified fraction of a second, or at least that no more than a small percentage of call setups last longer than a specified interval.
When applications with soft real time constraints are executed in an environment employing garbage collection, the garbage collector may also take the real time constraints into account. For example, some systems may allow users to specify soft real-time garbage collection objectives, such as an objective that garbage collection consume no more than “x” milliseconds of any “y” millisecond time slice. In order to attempt to meet such goals, garbage collection may be performed incrementally in such environments, and some portions of the garbage collector actions may be performed concurrently with mutator actions. In view of known trends in memory usage common to many types of applications, where the majority of unreachable objects in a heap tend to be recently allocated objects, generational and incremental garbage collection techniques may be combined for use with some applications with responsiveness constraints. For example, a garbage collector may be configured to classify heap regions into “young” regions (which may include the most recently allocated objects) and “non-young” regions, and select only a subset of the heap regions for collection during a given collection interval. Such a collector may, in general, identify and reclaim unreachable objects from young regions in preference to non-young regions, and may also reduce the overall overhead of garbage collection by maintaining different sets of garbage collection-related data structures for young regions and non-young regions (e.g., less information about cross-region references may be maintained for young regions). However, as more and more objects are allocated and modified by the mutating application, eventually, one or more non-young regions may have to be collected as well. Choices such as whether to include only young regions or both young and non-young regions in a collection set, and when to switch between collection sets that include non-young regions and collection sets that include only young regions, may have to be made carefully, taking the potential impact of the choices on application responsiveness into account.